A - Gaby And Addition Gym - 101466A --字典树 ，暴力+贪心

发表于 | 更新于 | 阅读次数：
本文字数： 4.9k | 阅读时长 ≈ 4 分钟

题目链接 ：http://codeforces.com/gym/101466/problem/A

A. Gaby And Addition

time limit per test

6.0 s

memory limit per test

1024 MB

input

standard input

output

standard output

Gaby is a little baby who loves playing with numbers. Recently she has learned how to add 2 numbers using the standard addition algorithm which we summarize in 3 steps:

  1. Line up the numbers vertically matching digits places.
  2. Add together the numbers that share the same place value from right to left.

  3. Carry if necessary. it means when adding two numbers we will get something like this:

    Unfortunately as Gaby is too young she doesn’t know what the third step means so she just omitted this step using her own standard algorithm (Gaby’s addition algorithm). When adding two numbers without carrying when necessary she gets something like the following:

    Gaby loves playing with numbers so she wants to practice the algorithm she has just learned (in the way she learned it) with a list of numbers adding every possible pair looking for the pair which generates the largest value and the smallest one.

    She needs to check if she is doing it correctly so she asks for your help to find the largest and the smallest value generated from the list of numbers using Gaby’s addition algorithm.

    Input

    The input starts with an integer _n_ (2 ≤ _n_ ≤ 106) indicating the number of integers Gaby will be playing with. The next line contains _n_numbers _ni_ (0 ≤ _ni_ ≤ 1018) separated by a single space.

    Output

    Output the smallest and the largest number you can get from adding two numbers from the list using Gaby’s addition algorithm.

    Examples

    input

    Copy

1
2
 6
17 5 11 0 42 99

output

Copy

1
0 99

input

Copy

1
2
 7
506823119072235413 991096248449924896 204242310783332529 778958050378192979 384042493592684633 942496553147499866 410043616343857825

output

Copy

1
52990443860776502 972190360051424498

Note

In the first sample input this is how you get the minimum and the maximum value

题意：给 n个数求不进位加法，两个数和的最大值，最小值。

题解：分别对每个数字拆分成 18个位，每个位是 0-9 的数字，然后用每个位建一个字典树。

就形成了一棵以0结点为根节点，然后每层分配0-9 儿子节点的字典树，然后每次查询和当前值相加最大值和最小值，分别每次从取模10最大的和最小的节点匹配。

例如 当前位是 5 最大值直接从当前位儿子节点 4开始找 如果存在直接求两个数的和，否则继续3 2 1.。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e6+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n;
int cnt=1;
struct Trie {
    int son[10];
    void init() {
        for(int i=0; i<10; i++) {
            son[i]=-1;
        }
    }
} tree[maxn*20];
ll p[20];
void insert(int r,int pos,ll val) {
    if(pos==-1)return ;
    ll v=val/p[pos]%10;
    if(tree[r].son[v]==-1) {
//        printf("%d",v);
        tree[cnt].init();
        tree[r].son[v]=cnt++;
    }
    insert(tree[r].son[v],pos-1,val);
}

ll findmx(int r,int pos,ll val) {
    if(pos==-1)return 0;
    ll v=val/p[pos]%10;
    for(int i=9-v; i>=0; i--) {
        if(tree[r].son[i]!=-1) {
            return (p[pos]*((v+i)%10))+findmx(tree[r].son[i],pos-1,val);
        }
    }
    for(int i=9; i>9-v; i--)
        if(tree[r].son[i]!=-1)
            return (p[pos]*((v+i)%10))+findmx(tree[r].son[i],pos-1,val);
}
ll findmi(int r,int pos,ll val) {
    if(pos==-1)return 0;
    int v=val/p[pos]%10;
    for(int i=10-v; i<=9; i++)
        if(tree[r].son[i]!=-1) {
            return (p[pos]*((v+i)%10))+findmi(tree[r].son[i],pos-1,val);
        }
    for(int i=0; i<10-v; i++)
        if(tree[r].son[i]!=-1)
            return (p[pos]*((v+i)%10))+findmi(tree[r].son[i],pos-1,val);
}
int main() {
    scanf("%d",&n);
    p[0]=1;
    for(int i=1; i<=18; i++) {
        p[i]=p[i-1]*10;
    }
    tree[0].init();
    ll mx=-1e18,mi=1e18;
    for(int i=0; i<n; i++) {
        ll x;
        scanf("%lld",&x);
        if(i!=0) {
            mi=min(mi,findmi(0,18,x));
            mx=max(mx,findmx(0,18,x));
        }
        insert(0,18,x);
//        puts("");
    }
    printf("%lld %lld\n",mi,mx);
    return 0;
}